package cn.xeblog.plugin.game.sudoku.algorithm;

import java.util.Arrays;
import java.util.Optional;
import java.util.Random;

/**
 * 解算器，能够解决给定{@link Grid}的数独
 * <p>
 * <a href="https://github.com/a11n/sudoku">来源</a>
 */
public class Solver {

    /**
     * 空
     */
    private static final int EMPTY = 0;

    /**
     * 值数组
     */
    private final int[] values;

    /**
     * 构造求解器实例
     */
    public Solver() {
        this.values = generateRandomValues();
    }

    /**
     * 使用回溯解算一个给定的{@link Grid}
     *
     * @param grid 要解算的 {@link Grid}
     * @throws IllegalStateException 如果提供的{@link Grid}无效，抛出.
     */
    public void solve(Grid grid) {
        // 是否可解算，且解算成功，true
        boolean solvable = solve(grid, grid.getFirstEmptyCell());

        // 网格不可解算时，抛出
        if (!solvable) {
            throw new IllegalStateException("The provided grid is not solvable.");
        } else {
            // 算法可能会出现有多个空值的情况 填补空值
            int size = grid.getSize();
            for (int i = 0; i < size; i++) {
                for (int j = 0; j < size; j++) {
                    Grid.Cell cell = grid.getCell(i, j);
                    if (cell.getValue() == 0) {
                        setEmptyValue(grid, cell);
                    }
                }
            }
        }
    }

    /**
     * 使用回溯解算一个给定的{@link Grid}
     *
     * @param grid 要解算的 {@link Grid}
     * @param cell 单元格
     * @return true，可解算，否则，false
     */
    private boolean solve(Grid grid, Optional<Grid.Cell> cell) {
        // 为空时，可解算
        if (!cell.isPresent()) {
            return true;
        }

        for (int value : values) {
            // 检查给定值是否对特定单元格有效,如果值在同一行、列和框中不存在，则该值是有效的
            if (grid.isValidValueForCell(cell.get(), value)) {
                cell.get().setValue(value);
                // 解算下一空单元格
                if (solve(grid, grid.getNextEmptyCellOf(cell.get()))) {
                    return true;
                }
                cell.get().setValue(EMPTY);
            }
        }

        return false;
    }

    /**
     * 生成随机值
     *
     * @return （0~9）10个数随机换位置后的一维数组
     */
    private int[] generateRandomValues() {
        int[] values = {EMPTY, 1, 2, 3, 4, 5, 6, 7, 8, 9};

        Random random = new Random();
        for (int i = 0, j = random.nextInt(9), tmp = values[j]; i < values.length; i++, j = random.nextInt(9), tmp = values[j]) {
            if (i == j) {
                continue;
            }
            // 换位置
            values[j] = values[i];
            values[i] = tmp;
        }

        return values;
    }

    /**
     * 处理算法未完成的空值
     *
     * @author ☆程序员鼓励师☆
     * @date 2022/8/16 10:41
     */
    public void setEmptyValue(Grid grid, Grid.Cell cell) {
        // 不为空，且值在同一行、列和框中不存在，即该值是有效的，设置该值
        Arrays.stream(values).filter(value -> value != EMPTY && grid.isValidValueForCell(cell, value)).forEach(cell::setValue);
    }
}
